#ifndef __JIENING_BPLUSTREE_HEAD__
#define __JIENING_BPLUSTREE_HEAD__

#include <stdio.h>
#include <string.h>
#include <vector>
#include "btree.h"
using namespace std;

/*
B+树的特征
B+树是B-树的变体，也是一种多路搜索树：
1、其定义基本与B-树同，除了：
2、非叶子结点的子树指针与关键字个数相同；
3、非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
4、为所有叶子结点增加一个链指针；
5、所有关键字都在叶子结点出现(如M=3)；
*/


template<class BTRKT, class BTRVT>
class jieningBplustree
{
public:
	// 构造函数theM>2
	jieningBplustree(unsigned int theM);

	// 添加节点到Btree,root node
	bool addKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>* kvInsert);

	// 添加节点到Btree,root node
	bool addKvp(const BTRKT& keyval);

	// 打印整个Btree的结构
	void doPrint(int level=0);

	// 在本节点的kv列表上的折半查找逻辑
	// equalpos: 返回和keyval相等的key的下标，如果没有相等的返回-1
	// insertpos: 返回keyval应该被插入的位置，如果找到有key和keyval相等，返回-1
	void findkey(const BTRKT& keyval, int& equalpos, int& insertpos);

	// 如果在以该节点为根的子树上找到有和keyval相同的值返回kvpair；没有找到返回NULL
	bool searchKeyPos(const BTRKT& keyval, struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, jieningBplustree*& targetNode, char* pathinf=NULL);

	// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上取出kvp，返回之，没有找到返回NULL
	bool searchToDeleteKV(const BTRKT& keyval, struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, char* pathinf=NULL);

	// 找寻并返回树中key值最小的kvp
	bool findMinKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, jieningBplustree*& targetNode);

	// 找寻并返回树中key值最大的kvp
	bool findMaxKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, jieningBplustree*& targetNode);

	// 以该节点为根的子树所有的关键字的个数之和
	unsigned getKeyCount();

	// 返回树中kvp的数量
	unsigned getKeyListLen(){return this->m_keyNum;}

	// 返回树是否是叶子节点
	bool isLeafNode(){return this->m_isLeaf;}

	jieningBplustree* getPreLeaf(){return (this->m_isLeaf ? this->m_preLeaf : NULL);}

	jieningBplustree* getPostLeaf(){return (this->m_isLeaf ? this->m_postLeaf : NULL);}
	
	// 检查树是否满足成为Btree的各种条件
	bool doTreeCheck();

	// 析构函数
	~jieningBplustree();

protected:
	
	bool doMegerChild(int mergepos);

	// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上取出kvp，返回之，没有找到返回NULL
	bool searchToDeleteKV(const BTRKT& keyval, BTRKT& minKey, struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, bool& needMerge);

	// 检查树是否满足成为Btree的各种条件,用于递归调用
	// isRoot：是否是从根节点开始检查
	// lp：该节点的左边的父kvp指针，如果没有设置为NULL，用于检查本节点kvp的key值是否比lp指向的大
	// rp：该节点的右边的父kvp指针，如果没有设置为NULL，用于检查本节点kvp的key值是否比rp指向的小
	// leaflevel：叶节点所在层次，初始值为-1，用于检查叶节点是否都处于同一层、
	// nowlevel：标示节点当前所在的层，0 base
	bool doTreeCheck(bool isRoot, jieningBtreeKVpair<BTRKT, BTRVT>* lp, jieningBtreeKVpair<BTRKT, BTRVT>* rp, int& leaflevel, int nowlevel);

	// 添加节点到Btree，如果因为kvlist的长度超过M-1,节点分裂，
	// minKey：带回插入新节点后最小key值
	// addParentKV：带回分裂后的中值
	// splitNode：指向分裂后的节点, 调用该函数的逻辑负责将splitNode添加到树中
	bool addKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>* insertKV, BTRKT& minKey, struct jieningBtreeKVpair<BTRKT, BTRVT>*& addParentKV, jieningBplustree*& splitNode);

	// 节点分裂逻辑，分裂的结果是产生一个新的节点，和一个分开新旧节点的kvp
	// splitnode：分裂出的新节点的指针，里面包含着较大的kvp
	// kvtoadd：一个分开新旧节点的kvp
	bool splitSelfNode(struct jieningBtreeKVpair<BTRKT, BTRVT>*& addParentKV, jieningBplustree*& splitnode);

	//===================================member variaties ===============================
	// 非叶子节点可以拥有的最大的子节点数
	const unsigned m_maxChildNum;

	// 节点实际拥有的kvp个数
	unsigned m_keyNum;

	// 存放kvp指针的数组, m_maxChildNum/2 <= list_size = m_keyNum <= m_maxChildNum-1
	struct jieningBtreeKVpair<BTRKT, BTRVT>** m_kvlist;

	// 非叶子节点存放子节点指针的数组, list_size=m_keyNum<=m_maxChildNum
	jieningBplustree** m_childlist;

	// 仅存在于叶节点中，指向前一个（包含较小的关键字）叶节点的指针
	jieningBplustree* m_preLeaf;

	// 仅存在于叶节点中，指向后一个（包含较大的关键字）叶节点的指针
	jieningBplustree* m_postLeaf;

	// 标识节点是否是叶子节点
	bool m_isLeaf;
};

//=======================================================================================
//=======================================================================================
//=======================================================================================

// 构造函数theM>2
template<class BTRKT, class BTRVT>
jieningBplustree<BTRKT, BTRVT>::jieningBplustree(unsigned int theM):
m_maxChildNum(theM>2?theM:3)
{
	//cout<<((long)this)<<" in jieningBtree::jieningBtree"<<endl;
	this->m_keyNum = 0;
	this->m_childlist = new jieningBplustree<BTRKT, BTRVT>*[this->m_maxChildNum+1];
	this->m_kvlist = new struct jieningBtreeKVpair<BTRKT, BTRVT>*[this->m_maxChildNum+1];

	for(unsigned int loop=0; loop<=this->m_maxChildNum; ++loop)
	{
		this->m_childlist[loop] = NULL;
		this->m_kvlist[loop] = NULL;
	}
	this->m_preLeaf = NULL;
	this->m_postLeaf = NULL;
	this->m_isLeaf = true;
}

// 节点分裂逻辑，分裂的结果是产生一个新的节点，和一个分开新旧节点的kvp
// splitnode：分裂出的新节点的指针，里面包含着较大的kvp
// kvtoadd：一个分开新旧节点的kvp
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::splitSelfNode(
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& addParentKV,
		jieningBplustree*& splitnode)
{
	if(this->m_keyNum <= (this->m_maxChildNum))
	{
		return false;
	}
	// key列表已经满载的处理逻辑
	// 分裂成两个叶节点，以下标为M/2的元素为界，当前节点保留M/2前面的元素
	// 分裂出的新叶子节点保留M/2后面的元素
	// kvtoadd 和 splitnode 返回给父节点做插入

	//breakpos分裂点，小于该下标值的元素保留，其余的移动到新节点
	unsigned int breakpos = this->m_keyNum/2;
	cout<<"in jieningBplustree::splitSelfNode, this->m_keyNum="<<this->m_keyNum<<", breakpos="<<breakpos<<endl;

	//breakpos分裂点kvp新做一个
	addParentKV = new struct jieningBtreeKVpair<BTRKT, BTRVT>(this->m_kvlist[breakpos]->thekey);

	// 移动breakpos之后的kvp和child到新节点
	splitnode = new jieningBplustree(this->m_maxChildNum);
	splitnode->m_isLeaf = this->m_isLeaf;
	unsigned int wcout = 0;
	for(unsigned int loop = breakpos; loop < this->m_keyNum; ++loop)
	{
		splitnode->m_kvlist[wcout] = this->m_kvlist[loop];
		this->m_kvlist[loop]  =NULL;
		if(!this->m_isLeaf)
		{
			splitnode->m_childlist[wcout] = this->m_childlist[loop];
			this->m_childlist[loop] = NULL;
		}
		splitnode->m_keyNum += 1;
		++wcout;
	}

	this->m_keyNum = (this->m_keyNum/2);

	// 修改叶子节点的前后指针
	if(this->m_isLeaf)
	{
		jieningBplustree* backnode = this->m_postLeaf;
		splitnode->m_postLeaf = backnode;
		splitnode->m_preLeaf = this;
		this->m_postLeaf = splitnode;

		if(NULL != backnode)
		{
			backnode->m_preLeaf = splitnode;
		}
	}

	return true;
}


// 添加节点到Btree，如果因为kvlist的长度超过M-1,节点分裂，
// insertKV：待插入的kvp
// minKey：带回插入新节点后最小key值
// addParentKV：带回分裂后的中值
// splitNode：指向分裂后的节点, 调用该函数的逻辑负责将splitNode添加到树中
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::addKvp(
		struct jieningBtreeKVpair<BTRKT, BTRVT>* insertKV,
		BTRKT& minKey,
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& addParentKV,
		jieningBplustree*& splitNode)
{
	//折半查找keyval该插入的位置insertpos
	int insertpos = -1;
	int equalpos = -1;
	this->findkey(insertKV->thekey, equalpos, insertpos);
	if(0 > insertpos)//
	{
		//cout<<"find keyval "<<keyval<<" already int keylist"<<endl;
		return false;
	}

	if(this->m_isLeaf)
	{
		//如果是叶节点，key列表还可以插入，
		//keyval该插入的位置为insertpos，移动insertpos之后的元素
		//cout<<"insertpos="<<insertpos<<endl;
		for(int loop=this->m_keyNum; loop > insertpos; --loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop-1];
		}
		this->m_kvlist[insertpos] = insertKV;
		this->m_keyNum += 1;

		if(this->m_keyNum > this->m_maxChildNum)
		{
			this->splitSelfNode(addParentKV, splitNode);
		}
	}
	else
	{
		insertpos = (insertpos-1 < 0) ? 0 : (insertpos-1);
		//如果是非叶节点，查找key列表，找到应该被插入的子节点，在子节点上递归调用该函数。
		jieningBplustree* keyAddNode = this->m_childlist[insertpos];
		if(NULL == keyAddNode)
		{
			return false;
		}

		struct jieningBtreeKVpair<BTRKT, BTRVT>* breakPoint = NULL;
		jieningBplustree* breakNode = NULL;
		if( ! keyAddNode->addKvp(insertKV, this->m_kvlist[insertpos]->thekey, breakPoint, breakNode))
		{
			return false;
		}

		if(NULL != breakNode)
		{
			//keyval该插入的位置为insertpos，移动insertpos之后的元素
			cout<<"insertpos="<<insertpos<<endl;
			for(int loop=this->m_keyNum; loop > insertpos+1; --loop)
			{
				this->m_kvlist[loop] = this->m_kvlist[loop-1];
				this->m_childlist[loop] = this->m_childlist[loop-1];
			}
			this->m_kvlist[insertpos+1] = breakPoint;
			this->m_childlist[insertpos+1] = breakNode;
			this->m_keyNum += 1;

			if(this->m_keyNum > this->m_maxChildNum)
			{
				this->splitSelfNode(addParentKV, splitNode);
			}
		}
	}

	minKey = this->m_kvlist[0]->thekey;

	return true;
}

// 添加节点到Btree,root node
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::addKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>* kvInsert)
{
	//cout<<"in jieningBtree::addKvp short,keyval="<<keyval<<" this->m_keyNum="<<this->m_keyNum<<endl;

	struct jieningBtreeKVpair<BTRKT, BTRVT>* kvtoadd = NULL;
	jieningBplustree* childtoadd=NULL;
	BTRKT minKey;
	if(!this->addKvp(kvInsert, minKey, kvtoadd, childtoadd))
	{
		return false;
	}

	if(NULL != childtoadd)
	{
		jieningBplustree* leftchild = new jieningBplustree(this->m_maxChildNum);
		leftchild->m_isLeaf = this->m_isLeaf;


		for(unsigned int loop=0; loop<this->m_keyNum; ++loop)
		{
			leftchild->m_kvlist[loop]=this->m_kvlist[loop];
			leftchild->m_childlist[loop]=this->m_childlist[loop];
			this->m_kvlist[loop] = NULL;
			this->m_childlist[loop] = NULL;
		}

		leftchild->m_keyNum = this->m_keyNum;
		leftchild->m_preLeaf = this->m_preLeaf;
		leftchild->m_postLeaf = this->m_postLeaf;

		this->m_preLeaf = NULL;
		this->m_postLeaf = NULL;
		this->m_isLeaf = false;
		this->m_kvlist[0] = new struct jieningBtreeKVpair<BTRKT, BTRVT>(minKey);
		this->m_childlist[0] = leftchild;
		this->m_kvlist[1] = kvtoadd;
		this->m_childlist[1] = childtoadd;
		this->m_keyNum = 2;
	}

	return true;
}

// 添加节点到Btree,root node
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::addKvp(const BTRKT& keyval)
{
	return this->addKvp(new struct jieningBtreeKVpair<BTRKT, BTRVT>(keyval));
}

// 打印整个Btree的结构
template<class BTRKT, class BTRVT>
void jieningBplustree<BTRKT, BTRVT>::doPrint(int level)
{
	if(0 == level)
	{
		cout<<endl<<"======================jieningBplustree::doPrint begin ========================="<<endl;
	}
	if(this->m_isLeaf)
	{
		for(int k=0;k<level;++k)
		{
			cout<<"\t";
		}
		cout<<"[[[[[[[[[[[[[[[[[[[["<<endl;
	}

	for(unsigned int loop=0; loop < this->m_keyNum; ++loop)
	{

		for(int k=0;k<level;++k)
		{
			cout<<"\t";
		}
		if(0 == loop)
		{
			cout<<"this->"<<((long)this)<<", "<<this->m_keyNum<<" keys, ";
			if(this->m_isLeaf)
			{
				cout<<"leaf node"<<endl;
			}
			else
			{
				cout<<(this->m_keyNum)<<" child nodes"<<endl;
			}
			for(int k=0;k<level;++k)
			{
				cout<<"\t";
			}
		}
		cout<<"key["<<loop<<"]="<<this->m_kvlist[loop]->thekey<<endl;
		if(NULL != this->m_childlist[loop])
		{
			this->m_childlist[loop]->doPrint(level+1);
		}
	}

	if(this->m_isLeaf)
	{
		for(int k=0;k<level;++k)
		{
			cout<<"\t";
		}
		cout<<"]]]]]]]]]]]]]]]]]]]]"<<endl;
	}
	if(0 == level)
	{
		cout<<endl<<"======================jieningBplustree::doPrint end ========================="<<endl;
	}
}

// 在本节点的kv列表上的折半查找逻辑
// equalpos: 返回和keyval相等的key的下标，如果没有相等的返回-1
// insertpos: 返回比keyval大的位置中最小的一个，如果找到有key和keyval相等，返回-1
//				keyval==0,keyval比现有的最小的key还小
//				keyval==this->m_keyNum,keyval比现有的最大的key还大
// 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
template<class BTRKT, class BTRVT>
void jieningBplustree<BTRKT, BTRVT>::findkey(const BTRKT& keyval, int& equalpos, int& insertpos)
{
	//如果是叶节点，key列表还可以插入的处理逻辑
	if (this->m_keyNum == 0)
	{
		equalpos = -1;
		insertpos = 0;
		return;
	}

	// 折半查找keyval该插入的位置insertpos
	int frompos = 0;
	int endpos = (this->m_keyNum - 1);
	int midpos;

	while (true)
	{
		if (this->m_kvlist[frompos]->thekey == keyval)
		{
			equalpos = frompos;
			insertpos = -1;
			return;
		}
		else if (this->m_kvlist[endpos]->thekey == keyval)
		{
			equalpos = endpos;
			insertpos = -1;
			return;
		}
		else if (keyval < this->m_kvlist[frompos]->thekey)
		{
			equalpos = -1;
			insertpos = frompos;
			return;
		}
		else if (this->m_kvlist[endpos]->thekey < keyval)
		{
			equalpos = -1;
			insertpos = endpos + 1;
			return;
		}
		else if (1 >= (endpos - frompos))
		{
			//起点和终点之间已经没有别的点
			insertpos = endpos;
			equalpos = -1;
			break;
		}
		else
		{
			midpos = (frompos + endpos) / 2;
			cout << "keyval=" << keyval << "\tfrompos=" << frompos
					<< "\tendpos=" << endpos << "\tmidpos=" << midpos << endl;
			if (this->m_kvlist[midpos]->thekey == keyval)
			{
				//如果在m_keylis中找到和keyval相等的值
				equalpos = midpos;
				insertpos = -1;
				return;
			}
			else if (this->m_kvlist[midpos]->thekey < keyval)
			{
				//如果中间点值比keyval小，起点设置为中间点
				//insertpos = midpos + 1;
				frompos = midpos;
			}
			else
			{
				//如果中间点值比keyval大，终点设置为中间点
				//insertpos = midpos;
				endpos = midpos;
			}
		}
	}

	return;
}

// 如果在以该节点为根的子树上找到有和keyval相同的值返回kvpair；没有找到返回NULL
// 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::searchKeyPos(
		const BTRKT& keyval,
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp,
		jieningBplustree*& targetNode,
		char* pathinf)
{
	//cout << "in jieningBplustree::searchKeyPos try to find keyval=" << keyval << endl;

	int insertpos = -1;
	int equalpos = -1;
	this->findkey(keyval, equalpos, insertpos);

	if(0 <= equalpos)
	{
		if (pathinf != NULL)
		{
			sprintf(pathinf, "%s -> %d", pathinf, equalpos);
		}
		if(this->m_isLeaf)
		{
			targetKvp = this->m_kvlist[equalpos];
			targetNode = this;
			return true;
		}
		else
		{
			return this->m_childlist[equalpos]->searchKeyPos(keyval, targetKvp, targetNode, pathinf);
		}
	}

	if(0 > (insertpos -1))
	{
		return false;
	}

	if (pathinf != NULL)
	{
		sprintf(pathinf, "%s -> %d", pathinf, insertpos-1);
	}

	if (this->m_isLeaf)
	{
		return false;
	}
	else
	{
		if(NULL != this->m_childlist[insertpos-1])
		{
			return this->m_childlist[insertpos-1]->searchKeyPos(keyval, targetKvp, targetNode, pathinf);
		}
	}

	return false;
}

// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上取出kvp，返回之，没有找到返回NULL
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::searchToDeleteKV(
		const BTRKT& keyval, 
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp,
		char* pathinf)
{
	cout<<"in searchToDeleteKV root, keyval="<<keyval<<endl;
	BTRKT minKey;
	bool needMerge = false;
	if( ! this->searchToDeleteKV(keyval, minKey, targetKvp, needMerge))
	{
		return false;
	}

	while(needMerge)
	{
		if(1 < this->m_keyNum)
		{
			break;
		}
		if(this->m_isLeaf)
		{
			break;
		}
		if(NULL == this->m_childlist[0])
		{
			break;
		}

		jieningBplustree* onlyChild = this->m_childlist[0];
		for(unsigned int loop=0; loop < onlyChild->m_keyNum; ++loop)
		{
			this->m_kvlist[loop] = onlyChild->m_kvlist[loop];
			onlyChild->m_kvlist[loop] = NULL;
			this->m_childlist[loop] = onlyChild->m_childlist[loop];
			onlyChild->m_childlist[loop] = NULL;
		}
		this->m_isLeaf = onlyChild->m_isLeaf;
		onlyChild->m_isLeaf = true;

		this->m_keyNum = onlyChild->m_keyNum;
		onlyChild->m_keyNum = 0;

		this->m_preLeaf = onlyChild->m_preLeaf;
		onlyChild->m_preLeaf = NULL;
		this->m_postLeaf = onlyChild->m_postLeaf;
		onlyChild->m_postLeaf = NULL;

		break;
	}

	return true;
}

// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上取出kvp，返回之，没有找到返回NULL
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::searchToDeleteKV(
		const BTRKT& keyval, 
		BTRKT& minKey,
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp,
		bool& needMerge)
{
	cout<<(long)this<<" in searchToDeleteKV , keyval="<<keyval<<endl;
	needMerge = false;
	int insertpos = -1;
	int equalpos = -1;
	this->findkey(keyval, equalpos, insertpos);
	
	if(this->m_isLeaf)
	{
		// 在叶节点没有找到相同的节点，搜索过程结束
		if(0>equalpos)
		{
			return false;
		}
		
		targetKvp = this->m_kvlist[equalpos];
		// 移动
		//kvpTakeOff = this->m_kvlist[equalpos];
		for(unsigned int loop = equalpos; loop < this->m_keyNum-1; ++loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop+1];
		}
		this->m_kvlist[this->m_keyNum-1] = NULL;
		this->m_keyNum -= 1;
		if(this->m_keyNum < this->m_maxChildNum/2)
		{
			needMerge = true;
		}
		if(this->m_keyNum>0)
		{
			minKey = this->m_kvlist[0]->thekey;
		}
		
		return true;
	}
	else
	{
		// b+tree所有值都在叶子节点，所以查找删除操作要一直递归到叶节点
		// searchChildPos, 递归遍历的节点
		int searchChildPos = -1;
		if(equalpos >= 0)
		{
			searchChildPos = equalpos;
		}
		else if(insertpos > 0)
		{
			searchChildPos = insertpos-1;
		}
		else
		{
			return false;
		}

		if(NULL == this->m_childlist[searchChildPos])
		{
			return false;
		}

		bool childNeedMerge = false;
		// 在下标为searchChildPos的子节点处，递归调用 查找删除 函数
		if( ! this->m_childlist[searchChildPos]->searchToDeleteKV(keyval, this->m_kvlist[searchChildPos]->thekey, targetKvp, childNeedMerge))
		{
			return false;
		}

		if(childNeedMerge)
		{
			if(!this->doMegerChild(searchChildPos))
			{
				cout<<"in searchToDeleteKV fail to call doMegerChild"<<endl;
			}
		}

		if(this->m_keyNum < this->m_maxChildNum/2)
		{
			needMerge = true;
		}
		if(this->m_keyNum>0)
		{
			minKey = this->m_kvlist[0]->thekey;
		}
	}
	return true;
}

// 找寻并返回树中key值最小的kvp
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::doMegerChild(int mergepos)
{
	cout<<(long)this<<" in doMegerChild"<<endl;

	int leftpos, rightpos;
	if(0 <= mergepos-1)
	{
		leftpos = mergepos-1;
		rightpos = mergepos;
	}
	else if(int(this->m_keyNum) > mergepos+1)
	{
		leftpos = mergepos;
		rightpos =  mergepos+1;
	}
	else
	{
		// 找不到两个待合并的子节点
		return false;
	}

	jieningBplustree* leftChild = this->m_childlist[leftpos];
	jieningBplustree* rightChild = this->m_childlist[rightpos];
	if(NULL == leftChild || NULL == rightChild)
	{
		// 两个待合并的子节点无效
		return false;
	}

	if(leftChild->m_keyNum >= this->m_maxChildNum/2 && rightChild->m_keyNum >= this->m_maxChildNum/2)
	{
		// 两个待合并的子节点拥有的节点数充足无须合并
		return false;
	}

	cout<<(long)this<<" in doMegerChild leftpos="<<leftpos<<", rightpos="<<rightpos<<endl;
	if(this->m_maxChildNum >= (leftChild->m_keyNum + rightChild->m_keyNum))
	{
		// 待合并的两个节点拥有kvp之和不足m_maxChildNum，righChild合并到leftChild成为一个节点
		cout<<(long)this<<" in doMegerChild merge rightchild into leftchild"<<endl;

		// 移动待合并的两个子节点 kvlist childlist
		for(unsigned int loop=0; loop < rightChild->m_keyNum; ++loop)
		{
			leftChild->m_kvlist[leftChild->m_keyNum+loop] = rightChild->m_kvlist[loop];
			rightChild->m_kvlist[loop] = NULL;
			leftChild->m_childlist[leftChild->m_keyNum+loop] = rightChild->m_childlist[loop];
			rightChild->m_childlist[loop] = NULL;
		}

		// 修改m_keyNum
		leftChild->m_keyNum += rightChild->m_keyNum;
		rightChild->m_keyNum = 0;

		// 修改前后叶子节点的指针保证叶子节点链条完整
		if(leftChild->m_isLeaf)
		{
			leftChild->m_postLeaf = rightChild->m_postLeaf;
			if(NULL != rightChild->m_postLeaf)
			{
				rightChild->m_postLeaf->m_preLeaf = leftChild;
			}
		}
		delete rightChild;

		// 移动本节点上的kvp和child
		for(unsigned int loop = rightpos; loop< this->m_keyNum-1; ++loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop+1];
			this->m_childlist[loop] = this->m_childlist[loop+1];
		}
		this->m_kvlist[this->m_keyNum-1] = NULL;
		this->m_childlist[this->m_keyNum-1] = NULL;
		this->m_keyNum -= 1;
	}
	else
	{
		int leftkvpnum = (leftChild->m_keyNum + rightChild->m_keyNum)/2;
		if(int(leftChild->m_keyNum) < leftkvpnum)
		{
			// 右子节点的kvp移动到左节点
			int movenum = leftkvpnum - leftChild->m_keyNum;
			cout<<(long)this<<" in doMegerChilda leftchild <--"<<movenum<<"-- rightchild"<<endl;

			for(int loop = 0; loop < movenum; ++loop)
			{
				leftChild->m_kvlist[leftChild->m_keyNum+loop] = rightChild->m_kvlist[loop];
				leftChild->m_childlist[leftChild->m_keyNum+loop] = rightChild->m_childlist[loop];
			}
			leftChild->m_keyNum = leftkvpnum;

			for(unsigned int loop = 0; loop < rightChild->m_keyNum; ++loop)
			{
				if(int(loop) < (int(rightChild->m_keyNum) - movenum))
				{
					rightChild->m_kvlist[loop] = rightChild->m_kvlist[loop+movenum];				
					rightChild->m_childlist[loop] = rightChild->m_childlist[loop+movenum];				
				}
				else
				{
					rightChild->m_kvlist[loop] = NULL;
					rightChild->m_childlist[loop] = NULL;
				}
			}
			rightChild->m_keyNum -= movenum;
			this->m_kvlist[rightpos]->thekey = rightChild->m_kvlist[0]->thekey;
		}
		else
		{
			// 左子节点的kvp移动到右节点
			int movenum = leftChild->m_keyNum - leftkvpnum;
			cout<<(long)this<<" in doMegerChilda leftchild --"<<movenum<<"--> rightchild"<<endl;

			for(int loop = rightChild->m_keyNum-1; loop >= 0; --loop)
			{
				if(loop >= movenum)
				{
					rightChild->m_kvlist[loop+movenum] = rightChild->m_kvlist[loop];				
					rightChild->m_childlist[loop+movenum] = rightChild->m_childlist[loop];				
				}
				else
				{
					rightChild->m_kvlist[loop] = NULL;
					rightChild->m_childlist[loop] = NULL;
				}
			}

			for(int loop =0; loop < movenum; ++loop)
			{	
				rightChild->m_kvlist[loop] = leftChild->m_kvlist[leftChild->m_keyNum + loop - movenum];
				leftChild->m_kvlist[leftChild->m_keyNum + loop - movenum] = NULL;

				rightChild->m_childlist[loop] = leftChild->m_childlist[leftChild->m_keyNum + loop - movenum];
				leftChild->m_childlist[leftChild->m_keyNum + loop - movenum] = NULL;

			}
			rightChild->m_keyNum += movenum;
			leftChild->m_keyNum -= movenum;
			this->m_kvlist[rightpos]->thekey = rightChild->m_kvlist[0]->thekey;
		}
	}

	return true;
}

// 找寻并返回树中key值最小的kvp
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::findMinKvp(
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp,
		jieningBplustree*& targetNode)
{
	if(this->m_isLeaf)
	{
		if(0 == this->m_keyNum)
		{
			return false;
		}
		if(NULL == this->m_kvlist[0])
		{
			return false;
		}
		targetKvp = this->m_kvlist[0];
		targetNode = this;
	}
	else
	{
		if(NULL == this->m_childlist[0])
		{
			return false;
		}
		return this->m_childlist[0]->findMinKvp(targetKvp, targetNode);	
	}
	return true;
}

// 找寻并返回树中key值最大的kvp
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::findMaxKvp(
		struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp,
		jieningBplustree*& targetNode)
{
	if(this->m_isLeaf)
	{
		if(0 == this->m_keyNum)
		{
			return false;
		}
		if(NULL == this->m_kvlist[this->m_keyNum-1])
		{
			return false;
		}
		targetKvp = this->m_kvlist[this->m_keyNum-1];
		targetNode = this;
	}
	else
	{
		if(NULL == this->m_childlist[this->m_keyNum-1])
		{
			return false;
		}
		return this->m_childlist[this->m_keyNum-1]->findMaxKvp(targetKvp, targetNode);	
	}
	return true;
}


// 以该节点为根的子树所有的关键字的个数之和
template<class BTRKT, class BTRVT>
unsigned jieningBplustree<BTRKT, BTRVT>::getKeyCount()
{
	int countnum = this->m_keyNum;
	if(!this->m_isLeaf)
	{
		for(unsigned int loop = 0; loop<this->m_keyNum; ++loop)
		{
			if(NULL != this->m_childlist[loop])
			{
				countnum += this->m_childlist[loop]->getKeyCount();
			}
		}
	}
	return countnum;
}

// 检查树是否满足成为Btree的各种条件
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::doTreeCheck()
{	
	cout<<"in public jieningBplustree::doTreeCheck"<<endl;
	int leaflevel=-1;
	bool rtn = this->doTreeCheck(true, NULL, NULL, leaflevel, 0);

	cout<<"in public jieningBplustree::doTreeCheck, leaflevel="<<leaflevel<<", checkre="<<rtn<<endl;

	return rtn;
}

// 检查树是否满足成为Btree的各种条件,用于递归调用
// isRoot：是否是从根节点开始检查
// lp：该节点的左边的父kvp指针，如果没有设置为NULL，用于检查本节点kvp的key值是否比lp指向的大
// rp：该节点的右边的父kvp指针，如果没有设置为NULL，用于检查本节点kvp的key值是否比rp指向的小
// leaflevel：叶节点所在层次，初始值为-1，用于检查叶节点是否都处于同一层、
// nowlevel：标示节点当前所在的层，0 base
template<class BTRKT, class BTRVT>
bool jieningBplustree<BTRKT, BTRVT>::doTreeCheck(
	bool isRoot, 
	jieningBtreeKVpair<BTRKT, BTRVT>* lp, 
	jieningBtreeKVpair<BTRKT, BTRVT>* rp, 
	int& leaflevel, 
	int nowlevel)
{
	cout<<((long)this)<<" in jieningBplustree::doTreeCheck "<<endl;
	// m_keyNum 在[M/2-1, M-1]之间,根节点的m_keyNum在[1, M-1]
	if(this->m_keyNum > this->m_maxChildNum)
	{
		cout<<"\tin jieningBplustree::doTreeCheck, find this->m_keyNum > this->m_maxChildNum"<<endl;
		return false;
	}
	if(this->m_keyNum < (this->m_maxChildNum/2))
	{
		if(!isRoot)
		{
			cout<<"\tin jieningBplustree::doTreeCheck, find this->m_keyNum < (this->m_maxChildNum/2)"<<endl;
			return false;
		}
	}

	// kvlist检查
	for(unsigned int loop=0; loop <= this->m_maxChildNum; ++loop)
	{
		if(loop < this->m_keyNum)
		{
			if(NULL == this->m_kvlist[loop])
			{
				cout<<"\tin jieningBplustree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", find NULL == this->m_kvlist["<<loop<<"]"<<endl;
				return false;
			}
			// key是按序排列的
			if(loop>0)
			{
				if(this->m_kvlist[loop]->thekey <= this->m_kvlist[loop-1]->thekey)
				{
					cout<<"\tin jieningBplustree::doTreeCheck, this->m_kvlist["<<loop<<"] <= this->m_kvlist["<<(loop-1)<<"]"<<endl;
					return false;
				}
			}
			// 所有的key的值都比 左父亲key值 不小
			if(NULL != lp)
			{
				if(lp->thekey > this->m_kvlist[loop]->thekey)
				{
					cout<<"\tin jieningBplustree::doTreeCheck, lp > this->m_kvlist["<<loop<<"]"<<endl;
					return false;
				}
			}
			// 所有的key的值都比右父亲key值小
			if(NULL != rp)
			{
				if(rp->thekey <= this->m_kvlist[loop]->thekey)
				{
					cout<<"\tin jieningBplustree::doTreeCheck, rp <= this->m_kvlist["<<loop<<"]"<<endl;
					return false;
				}
			}
		}
		else
		{
			if(NULL != this->m_kvlist[loop])
			{
				cout<<"\tin jieningBplustree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", find NULL != this->m_kvlist["<<loop<<"]"<<endl;
				return false;
			}
		}
	}
	
	// childlist检查
	if(this->m_isLeaf)
	{
		if(leaflevel < 0)
		{
			leaflevel = nowlevel;
		}
		if(leaflevel != nowlevel)
		{
			cout<<"\tin jieningBplustree::doTreeCheck, leafnode, nowlevel="<<nowlevel<<", but leaflevel="<<leaflevel<<endl;
			return false;
		}

		for(unsigned int loop=0; loop <= this->m_maxChildNum; ++loop)
		{
			if(NULL != this->m_childlist[loop])
			{
				cout<<"\tin jieningBplustree::doTreeCheck, leafnode, but find NULL !=this->m_childlist["<<loop<<"]"<<endl;
				return false;
			}
		}
	}
	else
	{
		for(unsigned int loop=0; loop <= this->m_maxChildNum; ++loop)
		{
			if(loop < this->m_keyNum)
			{
				if(NULL == this->m_childlist[loop])
				{
					cout<<"\tin jieningBplustree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", but find NULL==this->m_childlist["<<loop<<"]"<<endl;
					return false;
				}
				bool childcheckre = this->m_childlist[loop]->doTreeCheck(
					false,
					this->m_kvlist[loop],
					(loop < this->m_keyNum-1 ? this->m_kvlist[loop+1] : NULL),
					leaflevel,
					nowlevel+1);

				if(!childcheckre)
				{
					cout<<"\tin jieningBplustree::doTreeCheck child["<<loop<<"] return false"<<endl;
					return false;
				}
			}
			else
			{
				if(NULL != this->m_childlist[loop])
				{
					cout<<"\tin jieningBplustree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", but find NULL!=this->m_childlist["<<loop<<"]"<<endl;
					return false;
				}
			}
		}
	}

	return true;
}

// 析构函数
template<class BTRKT, class BTRVT>
jieningBplustree<BTRKT, BTRVT>::~jieningBplustree()
{
	//cout<<((long)this)<<" in jieningBplustree::~jieningBplustree, keylist size="<<this->m_keyNum<<endl;
	//this->doPrint();
	for(unsigned int loop=0; loop<this->m_maxChildNum; ++loop)
	{
		if(loop < this->m_keyNum )
		{
			//cout<<((long)this)<<" loop="<<loop<<", key="<<this->m_keylist[loop]<<endl;
			if(NULL != this->m_kvlist[loop])
			{
				delete this->m_kvlist[loop];
				this->m_kvlist[loop] = NULL;
			}
		}
		if(NULL != this->m_childlist)
		{
			if(NULL != this->m_childlist[loop])
			{
				//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete child loop="<<loop<<endl;
				delete this->m_childlist[loop];
				this->m_childlist[loop] = NULL;
			}
		}
	}

	if(NULL != this->m_childlist)
	{
		//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete this->m_childlist"<<endl;
		delete this->m_childlist;
		this->m_childlist = NULL;
	}

	if(NULL != this->m_kvlist)
	{
		//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete this->m_keylist"<<endl;
		delete this->m_kvlist;
		this->m_kvlist = NULL;
	}

	this->m_preLeaf = NULL;
	this->m_postLeaf = NULL;
	this->m_keyNum = 0;
}
#endif
